package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/study/live/717/5/10">
 * 二叉树的最大路径和 - 课后作业 牛客网</a>
 *
 * @author or2
 * @Description 给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
 * 这个路径的开始节点和结束节点可以是二叉树中的任意节点
 * @create 2021年09月09日 时间: 17:16
 */
public class MaxPathSum {

    /**
     * 记录最大路径
     */
    private int maxSum = Integer.MIN_VALUE;

    private static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }


    /**
     * @param root TreeNode类
     * @return int整型
     */
    public int maxPathSum(TreeNode root) {
        maxRoute(root);
        return maxSum;
    }

    private int maxRoute(TreeNode root) {
        if (root == null) {
            return 0;
        }

//        可能出现 权值为 负数!
        int leftMaxRoute = Math.max(maxRoute(root.left), 0);
        int rightMaxRoute = Math.max(maxRoute(root.right), 0);

        int curMaxPath = root.val + leftMaxRoute + rightMaxRoute;
        if (curMaxPath > maxSum) {
            maxSum = curMaxPath;
        }

        return root.val + Math.max(leftMaxRoute, rightMaxRoute);
    }
}
